#include <stdio.h>

void bubblingSort(int arr[], int n) {
    int i, j, temp;
    // 每次将一个元素送到末尾，n个元素，执行n次
    for (i = 0; i < n; ++i) {
        // 之前的循环已经将i个元素送到末尾，不需要再次比较，故减去，因为跟后一个元素比较，为了避免溢出，故减一
        for (j = 0; j < n - i - 1; ++j) {
            // 如果当前的元素比后一个元素小，就交换
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}
//冒泡排序涉及相邻两两数据的比较，
//故需要嵌套两层 for 循环来控制; 
//外层循环 n 次，
//内层最多时循环 n – 1次、
//最少循环 0 次，平均循环 (n-1)/2; 
//所以循环体内总的比较交换次数为：n* (n-1) / 2 = (n^2-n)/2 ;
// 按照计算时间复杂度的规则，去掉常数、去掉最高项系数，其复杂度为O (N^2) ; 
int main() {
    int i;
    int arr[10] = {20,11,16,8,3,5,9};
    bubblingSort(arr, 10);
    for (i = 0; i < 10; ++i) {
        printf("%d ", arr[i]);
    }
    return 0;
}